FLOW1 飞行员配对方案问题

模型：

二分图最大匹配->网络最大流

题意：

每架飞机需要两个驾驶员，一个正驾驶员和一个副驾驶员。由于种种原因，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。两个正驾驶员或两个副驾驶员都不能同机飞行。

题解：

二分图匹配裸题

代码：

#include <bits/stdc++.h>
#define fill(x,y) memset(x,y,sizeof x)
#define copy(x,y) memcpy(x,y,sizeof x)
using namespace std;
inline int read(int &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
inline void write(int x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int oo=0x7fffffff;
const int N=2000+5,M=N*N+5;
int en=1,h[N],d[N],na,nb,m,s,t,use,cur[N];
struct edge{int n,v,w;}e[M<<1];
inline void add(int x,int y,int z){e[++en]=(edge){h[x],y,z};h[x]=en;}
inline void exadd(int x,int y,int z){add(x,y,z);add(y,x,0);}
bool bfs(int s,int aim){
    fill(d,0);
    copy(cur,h);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].w){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}
int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].w){
            int tp=dfs(y,min(rest,e[i].w),aim);
            rest-=tp;
            e[i].w-=tp;
            e[i^1].w+=tp;
        }
    }
    return flow-rest;
}
int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}
signed main(){
    read(na);read(nb);
    nb-=na;
    for(int x,y;;){
        read(x);read(y);
        if(x==-1) break;
        exadd(x+1,y+1,1);
    }
    for(int i=1;i<=na;i++) exadd(1,i+1,1);
    for(int i=1;i<=nb;i++) exadd(na+1+i,na+nb+2,1);
    int ans=dinic(1,na+nb+2);
    if(ans==0){puts("No Solution!");return 0;}
    write(ans);puts("");
    for(int i=2;i<=en;i+=2){
        int x=e[i].v,y=e[i^1].v;
        if(x!=1&&y!=1&&x!=na+nb+2&&y!=na+nb+2&&e[i^1].w)
            write(y-1),putchar(' '),write(x-1),putchar('\n');
    }
}